#include <iostream>
#include <vector>
#define MAX_CHAR_SIZE 26
using namespace std;
class TrieNode
{
private:
public:
    bool isLeaf;
    TrieNode *child[MAX_CHAR_SIZE];
    TrieNode(/* args */) : isLeaf(false)
    {
        for (int i = 0; i < MAX_CHAR_SIZE; i++)
        {
            this->child[i] = nullptr;
        }
    }
    bool empty()
    {
        for (auto &p : child)
            if (!p)
                return false;
        return false;
    }
    ~TrieNode()
    {
        for (size_t i = 0; i < MAX_CHAR_SIZE; i++)
        {
            delete child[i];
        }
    }
};
class Trie
{
private:
    TrieNode *root;

public:
    Trie(/* args */)
    {
        root = new TrieNode();
    }
    void insert(string word)
    {
        TrieNode *p = root;
        for (char c : word)
        {
            int t = c - 'a';
            if (!p->child[t])
                p->child[t] = new TrieNode();
            p = p->child[t];
        }
        p->isLeaf = true;
    }
    bool search(string word)
    {
        TrieNode *p = root;
        for (char c : word)
        {
            int t = c - 'a';
            if (!p->child[t])
                return false;
            p = p->child[t];
        }
        return p->isLeaf;
    }
    bool startWith(string word)
    {
        TrieNode *p = root;
        for (char c : word)
        {
            int t = c - 'a';
            if (!p->child[t])
                return false;
            p = p->child[t];
        }
        return true;
    }

    bool haveChildren(TrieNode const *curr)
    {
        for (int i = 0; i < MAX_CHAR_SIZE; i++)
        {
            if (curr->child[i])
            {
                return true;
            }
        }
        return false;
    }

    void print(TrieNode *head)
    {
        int i = 0;
        while (head)
        {
            cout << head->child[i] + 'a' << "->";
            head = head->child[i + 1];
        }
    }
    ~Trie();
};

Trie::~Trie()
{
    delete root;
}

int main()
{
    /**
     * @brief 
     * 208. 实现 Trie (前缀树)
        648. 单词替换
        211. 添加与搜索单词 - 数据结构设计
        677. 键值映射
        676. 实现一个魔法字典
        745. 前缀和后缀搜索
     * 
     */
    Trie trie;
    trie.insert("hello");
    trie.insert("world");
    // trie.print();
    cout << trie.search("hello") << endl;
    cout << trie.startWith("he") << endl;
    system("pause");
    return 0;
}
